package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-25
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个有n个节点的 有向无环图（DAG），请你找出所有从节点 0到节点 n-1的路径并输出（不要求按特定顺序）
 *
 * 二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
 *
 * 译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。
 */
public class leetcode797 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] visited ;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        visited = new boolean[graph.length];
        path.add(0);
        dfs(0,graph.length-1,graph);
        return res;
    }
    public void dfs(int cur,int dst,int[][] graph){
        if (path.get(path.size()-1)==dst){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < graph[cur].length; i++) {
            if (!visited[graph[cur][i]]){
                path.add(graph[cur][i]);
                visited[graph[cur][i]] = true;
                dfs(graph[cur][i],dst,graph);
                path.remove(path.size()-1);
                visited[graph[cur][i]] = false;
            }
        }
    }
}
